package com.leetcode.LC_MED;

import java.util.Arrays;

public class LC53 {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int a = 0, b = 0, tmp = 0, max = 0;
        while (b < nums.length) {
            if (nums[a] < 0) {
                while (a < nums.length && nums[a] < 0) {
                    a++;
                }
                if (a == nums.length) {
                    break;
                }
                b = a;
                tmp = 0;
            }
            if ((tmp += nums[b]) >= 0) {
                max = Math.max(max, tmp);
                b++;
            } else {
                a=b;
            }
        }
        Arrays.sort(nums);
        if (nums[nums.length - 1] < 0) {
            max = nums[nums.length - 1];
        }
        return max;
    }

    public static int maxSubArray2(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int maxSubArray = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.length; i++){
            //sum要想有资格继续壮大 就必须大于 0 否则还不如恢复0
            sum = Math.max(sum,0);
            sum += nums[i];
            //maxSubArray始终取最大值
            maxSubArray = Math.max(sum,maxSubArray);
        }
        return maxSubArray;
    }

    public static void main(String[] args) {
        System.out.println(new LC53().maxSubArray2(new int[]{-2, -1}));
    }
}
